package leetcode.editor.cn;

public class Solution96 {
    //public int numTrees(int n) {
    //    return helper(1,n);
    //}
    //
    //int helper(int lo, int hi){
    //    if (lo>hi) return 1;
    //    int res = 0;
    //    for (int i=lo;i<=hi;i++){
    //        int left = helper(lo, i-1);
    //        int right = helper(i+1, hi);
    //        res += left*right;
    //    }
    //    return res;
    //}
    int [][] memo;
    public int numTrees(int n) {
        // 备忘录的值初始化为 0
        memo = new int[n + 1][n + 1];
        return helper(1,n);
    }

    int helper(int lo, int hi){
        if (lo>hi) return 1;
        // 查备忘录
        if (memo[lo][hi] != 0) {
            return memo[lo][hi];
        }
        int res = 0;
        for (int i=lo;i<=hi;i++){
            int left = helper(lo, i-1);
            int right = helper(i+1, hi);
            res += left*right;
        }
        memo[lo][hi] = res;
        return res;
    }
}
